﻿using System.Diagnostics;

namespace AlgorithmInterview.Chapter02._03;

/// <summary>
/// 给栈排序
/// </summary>
public class TestSort
{
    /// <summary>
    /// 把栈底元素移动到栈顶
    /// </summary>
    /// <param name="s">s栈的引用</param>
    private static void MoveBottomToTop(Stack<int> s)
    {
        if (s.Count <= 0) return;
        int top1 = s.Peek();
        s.Pop();
        if (s.Count > 0)
        {
            MoveBottomToTop(s);
            int top2 = s.Peek();
            if (top1 > top2)
            {
                s.Pop();
                s.Push(top1);
                s.Push(top2);
                return;
            }
        }

        s.Push(top1);
    }

    /// <summary>
    /// 排序
    /// </summary>
    /// <param name="s"></param>
    public static void Sort(Stack<int> s)
    {
        if (s.Count <= 0) return;
        // 把栈底元素移动到栈顶
        MoveBottomToTop(s);
        int top = s.Peek();
        s.Pop();
        // 递归处理子栈
        Sort(s);
        s.Push(top);
    }
}